import java.util.Arrays;
/*
*  直接插入排序
* */
public class InsertionSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { // 控制整个数组的循环
                int temp = arr[i]; // 假定 数组的第二位是有序的，所以把数组的第一位用来比较
                int j;
                for ( j = i-1; j >= 0 ; j--) { // 把 i 下标 之前的数进行排序
                    if (arr[j] > temp) { // 如果 要比较的数 大于 前一位，就把前一位的数值进行交换
                        arr[j+1] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j+1] = temp; // j 下标已经到了 -1 的位置
        }

    }

    public static void sort2(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i -1; j >= 0; j--) {
                if (arr[j] > temp) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = temp;
        }

    }

    public static void main(String[] args) {
        int[] arr = {7,5,6,4,3,1,2};
        int[] arr2 = {2,5,3,1};

      //  int[] arr2 = {18,24,5,72,64,65,81,82,1};
        sort2(arr);

//        for (int i: arr) {
//            System.out.print(i +" ");
//        }

        System.out.println(Arrays.toString(arr));
    }
}
